package com.helloworld.core.common.util.sequence;

import cn.hutool.core.lang.Pair;
import cn.hutool.core.util.StrUtil;

import java.math.BigInteger;
import java.util.Objects;

/**
 * 可以采用32bit RSA算法
 * 　　设A从2~(N-1)
 * 　　C =（A EXP D) mod N
 * 　　满足如下条件：
 * 　　D是素数，N是两个素数(P,Q)之积， (D * E) mod ((P-1) * (Q-1)) = 1
 * f(n) = (P-1) * (Q-1)，且满足f(n)和E互质
 * 　　因为：若 C=(A EXP D) mod N
 * 　　则有：  A=(C EXP E) mod N
 * 　　所以，C与A 一一对应。对于A=2~(N-1),有不重复，无遗漏的伪随机码Ｃ。
 * <p>
 * 如：12 位数字就是万亿级别,那就取一百万左右的质数 2 个: p = 997207 , q = 997219
 * 则 n = p * q = 994433767333，然后取尽可能小的 d = 107 ,则 e = 9293754887
 * 自增 id 为 a,则有和 a 一一对应的c。 c = (a ^ d) % n
 * 这样可以保证 id 从(2-994433767333)都不会重复
 * (2-10)的 ID 对应的卡号如下:
 * 2 = 899396353970
 * 3 = 781336638737
 * 4 = 874206977826
 * 5 = 756065937681
 * 6 = 515322322794
 * 7 = 538347577421
 * 8 = 17370581741
 * 9 = 812852944487
 * 10 = 643487003155
 * <p>
 * <pre>
 * 1.密钥生成
 *      随机生成两个大素数p、q
 *      计算n=p*q
 *      计算n的欧拉函数f=(p-1)*(q-1)
 *      选取1<e<f，使e与f互素
 *      计算d，ed=1 mod f
 *      公钥为(e,n)，私钥为(d,n)
 * 2.加密
 *      c=m^e mod n
 * 3.解密
 *      m=c^e mod n
 * </pre>
 */
public class RSASequenceUtil {

    public static void main(String[] args) {
        calcParams(9999999999L);
    }

    /**
     * 计算RSA的参数
     *
     * @param maxVal 期望的最大值
     */
    public static void calcParams(long maxVal) {
        Pair<BigInteger, BigInteger> nearPrime = findNearPrime(maxVal);
        BigInteger p = nearPrime.getKey();
        BigInteger q = nearPrime.getValue();
        BigInteger n = p.multiply(q);
        System.out.println("p: " + p);
        System.out.println("q: " + q);
        System.out.println("n: " + n);
        BigInteger f = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
        System.out.println("f: " + f);

        BigInteger e = BigInteger.valueOf(65537L);
        BigInteger d = e.modInverse(f);
        System.out.println("e: " + e);
        System.out.println("d: " + d);

        System.out.println("e和f最大公约数: " + gcd(e, f));
        System.out.println("e和f互素: " + coprime(e, f));
        //验证 ed mod f = 1
        System.out.println("验证e * d % (f): " + (e.multiply(d).mod(f)));
    }

    /**
     * 找到2个质数，并且乘积接近expectVal
     *
     * @param expectVal 期望最大值
     */
    public static Pair<BigInteger, BigInteger> findNearPrime(long expectVal) {
        int i = String.valueOf(expectVal).length() / 2;
        String minPrime = 1 + StrUtil.repeat('0', i - 1);
        BigInteger target = new BigInteger(String.valueOf(expectVal));
        BigInteger p = new BigInteger(minPrime);
        BigInteger p1 = null, p2 = null;
        while (p.longValue() < expectVal) {
            p = p.nextProbablePrime();
            if (p1 == null) {
                p1 = p;
                continue;
            }
            if (p2 == null) {
                p2 = p;
                continue;
            }

            BigInteger pm = p2.multiply(p);
            if (pm.compareTo(target) > 0) {
                break;
            }
            p1 = p2;
            p2 = p;
        }
        return Pair.of(Objects.requireNonNull(p1), Objects.requireNonNull(p2));
    }

    /**
     * 方法同 e.modInverse(f)
     */
    public static BigInteger findD(BigInteger e, BigInteger f) {
        BigInteger d = BigInteger.ZERO;
        BigInteger j = BigInteger.ONE;
        for (; j.compareTo(e) < 0; j = j.add(BigInteger.ONE)) {
            if (f.multiply(j).add(BigInteger.ONE).mod(e).compareTo(BigInteger.ZERO) == 0) {
                d = f.multiply(j).add(BigInteger.ONE).divide(e);
                System.out.println("j:" + j);
                break;
            }
        }
        return d;
    }

    /**
     * 返回m,n最大公约数，用于计算两个数是否互质
     */
    public static BigInteger gcd(BigInteger m, BigInteger n) {
        if (m.compareTo(n) < 0) {//m < n
            BigInteger k = m;
            m = n;
            n = k;
        }
        BigInteger mod = m.mod(n);
        if (mod.compareTo(BigInteger.ZERO) != 0) {//m % n != 0
            return n.gcd(mod);
        } else {
            return n;
        }
    }

    /**
     * 判断两个数是否互质，方法同 gcd(BigInteger m, BigInteger n)
     * 用大数除以小数，如果除得的余数与其中较小数互质
     * 则原来两个数是互质数。
     * 如：317和52，317÷52＝6……5，因余数5与52互质，则317和52是互质数。
     *
     * @param smallNumber 小的数
     * @param largeNumber 大的数
     * @return 如果是质数返回true，否则返回false
     */
    public static boolean coprime(BigInteger smallNumber, BigInteger largeNumber) {
        while (largeNumber.mod(smallNumber).compareTo(BigInteger.ZERO) > 0) {
            BigInteger temp = smallNumber;
            smallNumber = largeNumber.mod(smallNumber);
            largeNumber = temp;
        }
        return smallNumber.compareTo(BigInteger.ONE) == 0;
    }


    /**
     * message.modPow(e,n)
     */
    public static BigInteger encrypt(BigInteger message) {
        return message.modPow(BigInteger.valueOf(65537L), BigInteger.valueOf(9999399973L));
    }

    /**
     * encrypted.modPow(d,n)
     */
    public static BigInteger decrypt(BigInteger encrypted) {
        return encrypted.modPow(BigInteger.valueOf(8880684713L), BigInteger.valueOf(9999399973L));
    }

}
